%%%-------------------------------------------------------------------
%%% File    : p26.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% A unit fraction contains 1 in the numerator. The decimal 
%%% representation of the unit fractions with denominators 2 to 10 
%%% are given:
%%%
%%%     1/2	= 	0.5
%%%     1/3	= 	0.(3)
%%%     1/4	= 	0.25
%%%     1/5	= 	0.2
%%%     1/6	= 	0.1(6)
%%%     1/7	= 	0.(142857)
%%%     1/8	= 	0.125
%%%     1/9	= 	0.(1)
%%%     1/10	= 	0.1
%%% Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. 
%%% It can be seen that 1/7 has a 6-digit recurring cycle.
%%% Find the value of d < 1000 for which 1/d contains the 
%%% longest recurring cycle in its decimal fraction part.
%%%
%%% Created : 22 Dec 2008
%%%-------------------------------------------------------------------
-module(p26).

%% API
-compile(export_all).

%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function: solution(Max) -> {N, CycleLength}
%% Description: Returns the maximum cycle length of the numbers bellow 
%% Max
%%--------------------------------------------------------------------
solution(Max)->
    Self = self(),
    Collector = spawn(fun() -> collector(Self, 0, 0, 0, Max-1) end),
    lists:foreach(fun(I)-> spawn(fun() -> counter(Collector, I) end) end, lists:seq(1, Max-1)),
    receive
        Result -> Result
    end.


%%====================================================================
%% Internal functions
%%====================================================================
%Implements a process that calculates the cycle length of a single number 
%and sends the result to the collector.
counter(Collector, N) ->
    Collector ! {N, cycle_length(N)}.

%Implement a process that collects the results from all the calculations and returns the maximum cycle length.
collector(ParentPid, N, Max, MaxCount, MaxCount) -> 
    ParentPid ! {N, Max};
collector(ParentPid, N, Max, Count, MaxCount) ->
    receive
        {X, L} ->
            case L > Max of
                true ->
                    collector(ParentPid, X, L, Count + 1, MaxCount);
                _ -> 
                    collector(ParentPid, N, Max, Count + 1, MaxCount)
            end
    end.

%Returns the length of the cycle of 1/N or 0 (if N divides 1)
cycle_length(N)->
    next(10, N, ets:new(lookup, []), 0).

%Keep dividing until finished, or the 1st cycle is complete
%Uses a lookup table to check if at a cycle's end.
%This happens when the same divisible and divisor are reached, so 
%the table uses a tuple of {Divisible, Divisor} as a key. 
next(0, _, _, _) -> 0;
next(X, D, Tbl, Acc) ->
    Old = ets:lookup(Tbl, {X, D}),
    case Old of
        [] ->
            ets:insert(Tbl, {{X, D}, true}),
            next((X rem D) * 10, D, Tbl, Acc + 1);
        _ -> Acc
    end.
